package bag;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Creared with IntelliJ IDEA.
 * Description:
 * User:yxd
 * Date:2022-01-17
 * Time:16:50
 */
class TreeNode{
    public TreeNode left;
    public TreeNode right;

    public char val;
    public TreeNode(char val){
        this.val = val;
    }
}
public class BinaryTree {

    public TreeNode creat(){//创建 根节点
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');

        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        E.right = H;
        C.left = F;
        C.right = G;
        return A;

    }
    //前序遍历
     public void preorder(TreeNode root){
        if(root == null){
            return;
        }
        System.out.print(root.val);//先打印父亲节点 -》左子树-》右子树
        preorder(root.left);
        preorder(root.right);
    }
    //中序遍历
    public void inorder(TreeNode root){
        if(root == null){
            return;
        }
        inorder(root.left);
        System.out.print(root.val);//先打印左子树-》父亲节点 -》右子树
        inorder(root.right);
    }
    //后序遍历
    public void postorder(TreeNode root){
        if(root == null){
            return;
        }
        postorder(root.left);
        postorder(root.right);
        System.out.print(root.val);//先打印 左子树-》右子树-》父亲节点
    }
    //层序遍历
    public void level(TreeNode root){
        if(root == null)return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            System.out.print(cur.val + " ");
            if(cur.left != null){
                queue.offer(cur.left);
            }
            if(cur.right != null){
                queue.offer(cur.right);
            }
        }
    }
    //递归
    int count = 0;
    public int size(TreeNode root){
        if(root != null){
            count ++;
            size(root.left);
            size(root.right);
        }
        return count;
    }

    //所有节点
    public int size1(TreeNode root){//子问题思路
        int count = 0;
        if(root == null)return count;

        int count1 = size1(root.left);
        count += count1;
        int count2 = size1(root.right);
        count += count2;
        return count + 1;
    }

    //寻找叶子结点
    public int getLeafNodeCount(TreeNode root){
        if(root == null)return 0;
        if(root.left == null && root.right == null){
            return 1;//是叶子节点
        }
        return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
    }
    //寻找k层节点个数
    public int getKLevelNodeCount(TreeNode root,int k){
        if(root == null || k <= 0)return 0;
        if(k == 0){
            return 1;
        }
        return getKLevelNodeCount(root.left,k - 1) + getKLevelNodeCount(root.right,k-1);
    }
    //高度
    public int getHeight(TreeNode root){
        if(root == null)return 0;
        //空间复杂度是树的高度 时间复杂度是O(n) 空间复杂度（树的高度log2（n））
        return Math.max(getHeight(root.left) + 1,getHeight(root.right) + 1);//使用三目运算符一定不能让递归次数太多

    }
    //寻找某一节点
    public TreeNode find(TreeNode root,char val){
        if(root == null)return null;
        if(root.val == val)return root;//找到了就直接返回
        TreeNode ret = find(root.left,val);//左子树
        if(ret != null){
            return ret;
        }
        ret = find(root.right,val);//右子树
        if(ret != null){
            return ret;
        }
        return null;
    }
    public boolean isCompleteTree(TreeNode root){
        if(root == null)return false;
        Queue<TreeNode> qu = new LinkedList<>();
        qu.offer(root);//对列放入根节点
        while(!qu.isEmpty()){
            TreeNode cur = qu.poll();//每一个节点都出队 并记录下来
            if(cur != null){//如果不是空节点的话就放入左右孩子
                qu.offer(cur.left);
                qu.offer(cur.right);
            }else{//空了就退出循环
                break;
            }
        }
        while(!qu.isEmpty()){//判断剩下的里面还有没有不是空节点的节点 有的话就不是完全二叉树
            TreeNode node = qu.peek();
            if(node != null){
                return false;
            }
            qu.poll();
        }
        return true;
    }
    /*合并两二叉树
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1 == null ){
            return root2;
        }else if(root2 == null ){
            return root1;

        }
        TreeNode root = new TreeNode(root1.val + root2.val);//新的根节点放入两个节点之和
        root.left = mergeTrees(root1.left,root2.left);//左子树
        root.right = mergeTrees(root1.right,root2.right);//右子树
        return  root;

    }*/
    //比较两个二叉树是否相同 时间复杂度O(Min(M，N))
    public boolean isSameTree1(TreeNode p, TreeNode q) {
        if(p == null && q == null)return true;
        if((p == null && q != null) || (p != null && q == null) ){
            return false;
        }
        if(p.val != q.val){//如果值不相等说明就不是同一棵树
            return false;
        }
        return isSameTree1(p.left,q.left) && isSameTree1(p.right,q.right);//结构都相等
    }
    //判定两个二叉树是否是包含关系 时间复杂度O(M*N)
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root == null || subRoot == null){
            return false;
        }
        if(isSameTree(root,subRoot)){//同一棵树
            return true;
        }
        if(isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot)){
            return true;//左子树或者右子树
        }
        return  false;
    }
    public static boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null)return true;
        if((p == null && q != null) || (p != null && q == null) ){
            return false;
        }
        if(p.val != q.val){//如果值不相等说明就不是同一棵树
            return false;
        }
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);//结构都相等
    }
    //判定一个二叉树是否是平衡二叉树
    public boolean isBalanced(TreeNode root) {
        if(root == null)return true;
        return maxDepth(root) >= 0;//如果是负数，证明 有小树不满足，不是平衡二叉树
    }
    public static int maxDepth(TreeNode root) {
        if(root == null)return 0;
        int l = maxDepth(root.left);
        int r = maxDepth(root.right);
        if(l >= 0 && r >= 0 && Math.abs(l - r) <= 1){//在求每棵树 的深度的时候都判断一下，如果有一棵树不满足了，
            // 整棵树就不是平衡二叉树了，就可以直接返回负数，所以在判断条件中需要加判断深度是否为负数
            return Math.max(l + 1,r + 1);
        }else{
            return -2;
        }
    }
    //判定一个二叉树是否是对称
    public boolean isSymmetricChild(TreeNode l,TreeNode r){
        if(l == null && r== null){
            return true;
        }
        if(l == null && r != null){
            return false;
        }
        if(l != null && r == null){
            return false;
        }
        if(l.val != r.val){//值不相等就返回
            return false;
        }
        return isSymmetricChild(l.left,r.right) && isSymmetricChild(l.right,r.left);//左右子树是否对称
    }
    public boolean isSymmetric(TreeNode root) {
        if(root == null)return true;
        return isSymmetricChild(root.left,root.right);
    }
    //二叉树的层序遍历, 返回二维List
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();//存放所有的元素
        if(root == null) return ret;
        Queue<TreeNode> queue = new LinkedList<>();//利用队列
        queue.offer(root);//放入根节点
        while(!queue.isEmpty()){
            int size = queue.size();//当前层有多少个节点
            List<Integer> list = new ArrayList<>();//每一层
            while(size != 0){
                TreeNode cur = queue.poll();//出队并存储下来
                //list.add(cur.val);//放入list 这里的val类型不一样，所以会报错
                if(cur.left != null){
                    queue.offer(cur.left);
                }
                if(cur.right != null){
                    queue.offer(cur.right);
                }
                size--;//完成一个节点就减一
            }
            ret.add(list);//放入每一层
        }
        return ret;
    }
}
